home *** CD-ROM | disk | FTP | other *** search
/ Group 42-Sells Out! - The Information Archive / Group 42 Sells Out (Group 42) (1996).iso / crypto / skipjack.txt < prev    next >
Text File  |  1995-11-30  |  27KB  |  603 lines

  1.  
  2. [ Permission to make this document available was obtained
  3.   directly from Dorothy Denning.  -- MODERATOR ]
  4.  
  5.  
  6.                             Skipjack Review
  7.                                     
  8.                              Interim Report
  9.                                     
  10.                         The SKIPJACK Algorithm
  11.  
  12.  
  13.            Ernest F. Brickell, Sandia National Laboratories
  14.                Dorothy E. Denning, Georgetown University
  15.             Stephen T. Kent, BBN Communications Corporation
  16.                           David P. Maher, AT&T
  17.                   Walter Tuchman, Amperif Corporation
  18.                                     
  19.                               July 28, 1993
  20.  
  21.                             (copyright 1993)
  22.  
  23.  
  24. Executive Summary
  25.  
  26. The objective of the SKIPJACK review was to provide a mechanism whereby
  27. persons outside the government could evaluate the strength of the
  28. classified encryption algorithm used in the escrowed encryption devices
  29. and publicly report their findings.  Because SKIPJACK is but one
  30. component of a large, complex system, and because the security of
  31. communications encrypted with SKIPJACK depends on the security of the
  32. system as a whole, the review was extended to encompass other
  33. components of the system.  The purpose of this Interim Report is to
  34. report on our evaluation of the SKIPJACK algorithm.  A later Final
  35. Report will address the broader system issues.
  36.  
  37. The results of our evaluation of the SKIPJACK algorithm are as
  38. follows:
  39.  
  40.   1. Under an assumption that the cost of processing power is halved
  41.      every eighteen months, it will be 36 years before the cost of
  42.      breaking SKIPJACK by exhaustive search will be equal to the cost
  43.      of breaking DES today.  Thus, there is no significant risk that
  44.      SKIPJACK will be broken by exhaustive search in the next 30-40
  45.      years.
  46.  
  47.   2. There is no significant risk that SKIPJACK can be broken through a
  48.      shortcut method of attack.
  49.  
  50.   3. While the internal structure of SKIPJACK must be classified in
  51.      order to protect law enforcement and national security objectives,
  52.      the strength of SKIPJACK against a cryptanalytic attack does not
  53.      depend on the secrecy of the algorithm.
  54.  
  55.  
  56.  
  57. 1.  Background
  58.  
  59. On April 16, the President announced a new technology initiative aimed
  60. at providing a high level of security for sensitive, unclassified
  61. communications, while enabling lawfully authorized intercepts of
  62. telecommunications by law enforcement officials for criminal
  63. investigations.  The initiative includes several components:
  64.  
  65.     A classified encryption/decryption algorithm called "SKIPJACK."
  66.  
  67.     Tamper-resistant cryptographic devices (e.g., electronic chips),
  68.     each of which contains SKIPJACK, classified control software, a
  69.     device identification number, a family key used by law enforcement,
  70.     and a device unique key that unlocks the session key used to
  71.     encrypt a particular communication.
  72.  
  73.     A secure facility for generating device unique keys and programming
  74.     the devices with the classified algorithms, identifiers, and keys.
  75.  
  76.     Two escrow agents that each hold a component of every device unique
  77.     key.  When combined, those two components form the device unique
  78.     key.
  79.  
  80.     A law enforcement access field (LEAF), which enables an authorized
  81.     law enforcement official to recover the session key.  The LEAF is
  82.     created by a device at the start of an encrypted communication and
  83.     contains the session key encrypted under the device unique key
  84.     together with the device identifier, all encrypted under the family
  85.     key.
  86.  
  87.     LEAF decoders that allow an authorized law enforcement official to
  88.     extract the device identifier and encrypted session key from an
  89.     intercepted LEAF.  The identifier is then sent to the escrow
  90.     agents, who return the components of the corresponding device
  91.     unique key.  Once obtained, the components are used to reconstruct
  92.     the device unique key, which is then used to decrypt the session
  93.     key.
  94.  
  95. This report reviews the security provided by the first component,
  96. namely the SKIPJACK algorithm.  The review was performed pursuant to
  97. the President's direction that "respected experts from outside the
  98. government will be offered access to the confidential details of the
  99. algorithm to assess its capabilities and publicly report their
  100. finding."  The Acting Director of the National Institute of Standards
  101. and Technology (NIST) sent letters of invitation to potential
  102. reviewers.  The authors of this report accepted that invitation.
  103.  
  104. We attended an initial meeting at the Institute for Defense Analyses
  105. Supercomputing Research Center (SRC) from June 21-23.  At that meeting,
  106. the designer of SKIPJACK provided a complete, detailed description of
  107. the algorithm, the rationale for each feature, and the history of the
  108. design.  The head of the NSA evaluation team described the evaluation
  109. process and its results.  Other NSA staff briefed us on the LEAF
  110. structure and protocols for use, generation of device keys, protection
  111. of the devices against reverse engineering, and NSA's history in the
  112. design and evaluation of encryption methods contained in SKIPJACK.
  113. Additional NSA and NIST staff were present at the meeting to answer our
  114. questions and provide assistance.  All staff members were forthcoming
  115. in providing us with requested information.
  116.  
  117. At the June meeting, we agreed to integrate our individual evaluations
  118. into this joint report.  We also agreed to reconvene at SRC from July
  119. 19-21 for further discussions and to complete a draft of the report.
  120. In the interim, we undertook independent tasks according to our
  121. individual interests and availability.  Ernest Brickell specified a
  122. suite of tests for evaluating SKIPJACK.  Dorothy Denning worked at NSA
  123. on the refinement and execution of these and other tests that took into
  124. account suggestions solicited from Professor Martin Hellman at Stanford
  125. University.  NSA staff assisted with the programming and execution of
  126. these tests.  Denning also analyzed the structure of SKIPJACK and its
  127. susceptibility to differential cryptanalysis.  Stephen Kent visited NSA
  128. to explore in more detail how SKIPJACK compared with NSA encryption
  129. algorithms that he already knew and that were used to protect
  130. classified data.  David Maher developed a risk assessment approach
  131. while continuing his ongoing work on the use of the encryption chip in
  132. the AT&T Telephone Security Device.  Walter Tuchman investigated the
  133. anti-reverse engineering properties of the chips.
  134.  
  135. We investigated more than just SKIPJACK because the security of
  136. communications encrypted with the escrowed encryption technology
  137. depends on the security provided by all the components of the
  138. initiative, including protection of the keys stored on the devices,
  139. protection of the key components stored with the escrow agents, the
  140. security provided by the LEAF and LEAF decoder, protection of keys
  141. after they have been transmitted to law enforcement under court order,
  142. and the resistance of the devices to reverse engineering.  In addition,
  143. the success of the technology initiative depends on factors besides
  144. security, for example, performance of the chips.  Because some
  145. components of the escrowed encryption system, particularly the key
  146. escrow system, are still under design, we decided to issue this Interim
  147. Report on the security of the SKIPJACK algorithm and to defer our Final
  148. Report until we could complete our evaluation of the system as a
  149. whole.
  150.  
  151.  
  152. 2.  Overview of the SKIPJACK Algorithm
  153.  
  154. SKIPJACK is a 64-bit "electronic codebook" algorithm that transforms a
  155. 64-bit input block into a 64-bit output block.  The transformation is
  156. parameterized by an 80-bit key, and involves performing 32 steps or
  157. iterations of a complex, nonlinear function.  The algorithm can be used
  158. in any one of the four operating modes defined in FIPS 81 for use with
  159. the Data Encryption Standard (DES).
  160.  
  161. The SKIPJACK algorithm was developed by NSA and is classified SECRET.
  162. It is representative of a family of encryption algorithms developed in
  163. 1980 as part of the NSA suite of "Type I" algorithms, suitable for
  164. protecting all levels of classified data.  The specific algorithm,
  165. SKIPJACK, is intended to be used with sensitive but unclassified
  166. information.
  167.  
  168. The strength of any encryption algorithm depends on its ability to
  169. withstand an attack aimed at determining either the key or the
  170. unencrypted ("plaintext") communications.  There are basically two
  171. types of attack, brute-force and shortcut.
  172.  
  173.  
  174. 3.  Susceptibility to Brute Force Attack by Exhaustive Search
  175.  
  176. In a brute-force attack (also called "exhaustive search"), the
  177. adversary essentially tries all possible keys until one is found that
  178. decrypts the intercepted communications into a known or meaningful
  179. plaintext message.  The resources required to perform an exhaustive
  180. search depend on the length of the keys, since the number of possible
  181. keys is directly related to key length.  In particular, a key of length
  182. N bits has 2^N possibilities.  SKIPJACK uses 80-bit keys, which means
  183. there are 2^80 (approximately 10^24) or more than 1 trillion trillion
  184. possible keys.
  185.  
  186. An implementation of  SKIPJACK optimized for a single processor on the
  187. 8-processor Cray YMP performs about 89,000 encryptions per second.  At
  188. that rate, it would take more than 400 billion years to try all keys.
  189. Assuming the use of all 8 processors and aggressive vectorization, the
  190. time would be reduced to about a billion years.
  191.  
  192. A more speculative attack using a future, hypothetical, massively
  193. parallel machine with 100,000 RISC processors, each of which was
  194. capable of 100,000 encryptions per second, would still take about 4
  195. million years.  The cost of such a machine might be on the order of $50
  196. million.  In an even more speculative attack, a special purpose machine
  197. might be built using 1.2 billion $1 chips with a 1 GHz clock.  If the
  198. algorithm could be pipelined so that one encryption step were performed
  199. per clock cycle, then the $1.2 billion machine could exhaust the key
  200. space in 1 year.
  201.  
  202. Another way of looking at the problem is by comparing a brute force
  203. attack on SKIPJACK with one on DES, which uses 56-bit keys.  Given that
  204. no one has demonstrated a capability for breaking DES, DES offers a
  205. reasonable benchmark.  Since SKIPJACK keys are 24 bits longer than DES
  206. keys, there are 2^24 times more possibilities.  Assuming that the cost
  207. of processing power is halved every eighteen months, then it will not
  208. be for another 24 * 1.5 = 36 years before the cost of breaking
  209. SKIPJACK is equal to the cost of breaking DES today.  Given the lack of
  210. demonstrated capability for breaking DES, and the expectation that the
  211. situation will continue for at least several more years, one can
  212. reasonably expect that SKIPJACK will not be broken within the next
  213. 30-40 years.
  214.  
  215. Conclusion 1:   Under an assumption that the cost of processing power
  216. is halved every eighteen months, it will be 36 years before the cost of
  217. breaking SKIPJACK by exhaustive search will be equal to the cost of
  218. breaking DES today.  Thus, there is no significant risk that SKIPJACK
  219. will be broken by exhaustive search in the next 30-40 years.
  220.  
  221. 4.  Susceptibility to Shortcut Attacks
  222.  
  223. In a shortcut attack, the adversary exploits some property of the
  224. encryption algorithm that enables the key or plaintext to be determined
  225. in much less time than by exhaustive search.  For example, the RSA
  226. public-key encryption method is attacked by factoring a public value
  227. that is the product of two secret primes into its primes.
  228.  
  229. Most shortcut attacks use probabilistic or statistical methods that
  230. exploit a structural weakness, unintentional or intentional (i.e., a
  231. "trapdoor"), in the encryption algorithm.  In order to determine
  232. whether such attacks are possible, it is necessary to thoroughly
  233. examine the structure of the algorithm and its statistical properties.
  234. In the time available for this review, it was not feasible to conduct
  235. an evaluation on the scale that NSA has conducted or that has been
  236. conducted on the DES.  Such review would require many man-years of
  237. effort over a considerable time interval.  Instead, we concentrated on
  238. reviewing NSA's design and evaluation process.  In addition, we
  239. conducted several of our own tests.
  240.  
  241. 4.1  NSA's Design and Evaluation Process
  242.  
  243. SKIPJACK was designed using building blocks and techniques that date
  244. back more than forty years.  Many of the techniques are related to work
  245. that was evaluated by some of the world's most accomplished and famous
  246. experts in combinatorics and abstract algebra.  SKIPJACK's more
  247. immediate heritage dates to around 1980, and its initial design to
  248. 1987.
  249.  
  250. SKIPJACK was designed to be evaluatable, and the design and evaluation
  251. approach was the same used with algorithms that protect the country's
  252. most sensitive classified information.  The specific structures
  253. included in SKIPJACK have a long evaluation history, and the
  254. cryptographic properties of those structures had many prior years of
  255. intense study before the formal process began in 1987.  Thus, an
  256. arsenal of tools and data was available.  This arsenal was used by
  257. dozens of adversarial evaluators whose job was to break SKIPJACK.  Many
  258. spent at least a full year working on the algorithm.  Besides highly
  259. experienced evaluators, SKIPJACK was subjected to cryptanalysis by less
  260. experienced evaluators who were untainted by past approaches.  All
  261. known methods of attacks were explored, including differential
  262. cryptanalysis.  The goal was a design that did not allow a shortcut
  263. attack.
  264.  
  265. The design underwent a sequence of iterations based on feedback from
  266. the evaluation process.  These iterations eliminated properties which,
  267. even though they might not allow successful attack, were related to
  268. properties that could be indicative of vulnerabilities.  The head of
  269. the NSA evaluation team confidently concluded "I believe that SKIPJACK
  270. can only be broken by brute force   there is no better way."
  271.  
  272. In summary, SKIPJACK is based on some of NSA's best technology.
  273. Considerable care went into its design and evaluation in accordance
  274. with the care given to algorithms that protect classified data.
  275.  
  276. 4.2  Independent Analysis and Testing
  277.  
  278. Our own analysis and testing increased our confidence in the strength
  279. of SKIPJACK and its resistance to attack.
  280.  
  281. 4.2.1  Randomness and Correlation Tests
  282.  
  283. A strong encryption algorithm will behave like a random function of the
  284. key and plaintext so that it is impossible to determine any of the key
  285. bits or plaintext bits from the ciphertext bits (except by exhaustive
  286. search).  We ran two sets of tests aimed at determining whether
  287. SKIPJACK is a good pseudo random number generator.  These tests were
  288. run on a Cray YMP at NSA.  The results showed that SKIPJACK behaves
  289. like a random function and that ciphertext bits are not correlated with
  290. either key bits or plaintext bits.  Appendix A gives more details.
  291.  
  292. 4.2.2  Differential Cryptanalysis
  293.  
  294. Differential cryptanalysis is a powerful method of attack that exploits
  295. structural properties in an encryption algorithm.  The method involves
  296. analyzing the structure of the algorithm in order to determine the
  297. effect of particular differences in plaintext pairs on the differences
  298. of their corresponding ciphertext pairs, where the differences are
  299. represented by the exclusive-or of the pair.  If it is possible to
  300. exploit these differential effects in order to determine a key in less
  301. time than with exhaustive search, an encryption algorithm is said to be
  302. susceptible to differential cryptanalysis.  However, an actual attack
  303. using differential cryptanalysis may require substantially more chosen
  304. plaintext than can be practically acquired.
  305.  
  306. We examined the internal structure of SKIPJACK to determine its
  307. susceptibility to differential cryptanalysis.  We concluded it was not
  308. possible to perform an attack based on differential cryptanalysis in
  309. less time than with exhaustive search.
  310.  
  311. 4.2.3  Weak Key Test
  312.  
  313. Some algorithms have "weak keys" that might permit a shortcut
  314. solution.  DES has a few weak keys, which follow from a pattern of
  315. symmetry in the algorithm.  We saw no pattern of symmetry in the
  316. SKIPJACK algorithm which could lead to weak keys.  We also
  317. experimentally tested the all "0" key (all 80 bits are "0") and the all
  318. "1" key to see if they were weak and found they were not.
  319.  
  320. 4.2.4  Symmetry Under Complementation Test
  321.  
  322. The DES satisfies the property that for a given plaintext-ciphertext
  323. pair and associated key, encryption of the one's complement of the
  324. plaintext with the one's complement of the key yields the one's
  325. complement of the ciphertext.  This "complementation property" shortens
  326. an attack by exhaustive search by a factor of two since half the keys
  327. can be tested by computing complements in lieu of performing a more
  328. costly encryption.  We tested SKIPJACK for this property and found that
  329. it did not hold.
  330.  
  331. 4.2.5  Comparison with Classified Algorithms
  332.  
  333. We compared the structure of SKIPJACK to that of NSA Type I algorithms
  334. used in current and near-future devices designed to protect classified
  335. data.  This analysis was conducted with the close assistance of the
  336. cryptographer who developed SKIPJACK and included an in-depth
  337. discussion of design rationale for all of the algorithms involved.
  338. Based on this comparative, structural analysis of SKIPJACK against
  339. these other algorithms, and a detailed discussion of the similarities
  340. and differences between these algorithms, our confidence in the basic
  341. soundness of SKIPJACK was further increased.
  342.  
  343. Conclusion 2:  There is no significant risk that SKIPJACK can be broken
  344. through a shortcut method of attack.
  345.  
  346.  
  347. 5.   Secrecy of the Algorithm
  348.  
  349. The SKIPJACK algorithm is sensitive for several reasons.  Disclosure of
  350. the algorithm would permit the construction of devices that fail to
  351. properly implement the LEAF, while still interoperating with legitimate
  352. SKIPJACK devices.  Such devices would provide high quality
  353. cryptographic security without preserving the law enforcement access
  354. capability that distinguishes this cryptographic initiative.
  355. Additionally, the SKIPJACK algorithm is classified SECRET   NOT
  356. RELEASABLE TO FOREIGN NATIONALS.  This classification reflects the high
  357. quality of the algorithm, i.e., it incorporates design techniques that
  358. are representative of algorithms used to protect classified
  359. information.  Disclosure of the algorithm would permit analysis that
  360. could result in discovery of these classified design techniques, and
  361. this would be detrimental to national security.
  362.  
  363. However, while full exposure of the internal details of SKIPJACK would
  364. jeopardize law enforcement and national security objectives, it would
  365. not jeopardize the security of encrypted communications.  This is
  366. because a shortcut attack is not feasible even with full knowledge of
  367. the algorithm.  Indeed, our analysis of the susceptibility of SKIPJACK
  368. to a brute force or shortcut attack was based on the assumption that
  369. the algorithm was known.
  370.  
  371. Conclusion 3:  While the internal structure of SKIPJACK must be
  372. classified in order to protect law enforcement and national security
  373. objectives, the strength of SKIPJACK against a cryptanalytic attack
  374. does not depend on the secrecy of the algorithm.
  375.  
  376. --------------------------------------------------------------------------
  377. LaTeX Appendix
  378. --------------
  379. \documentstyle{article}
  380. \textheight 8.25in
  381. \topmargin -.25in
  382. \textwidth 6.5in
  383. \oddsidemargin 0in
  384. \begin{document}
  385. \parskip .25in
  386. \large
  387. \raggedright
  388. \setcounter{page}{8}
  389. \centerline{\bf Appendix A}
  390.  
  391. {\bf A.1 Cycle Structure Tests}
  392.  
  393. The first set of tests examined the cycle structure of SKIPJACK.  Fix
  394. a set of keys, $\cal K$, a plaintext, $m$, and a function $h\; : \;
  395. {\cal M} \longrightarrow {\cal K}$, where ${\cal M}$ is the set of all
  396. 64 bit messages.  Let $f \; : \; {\cal K} \longrightarrow {\cal K}$ be
  397. defined as $f(k) = h ( SJ(k,m))$ (where $SJ(k,m)$ denotes the SKIPJACK
  398. encryption of plaintext $m$ with key $k$).  Let $N = |\cal K|$.  The
  399. expected cycle length of $f$ is $\sqrt{\pi N /8}$.  We chose sets of
  400. $\cal K$ with $N \; = \; 2^{10}, 2^{16}, 2^{24}, 2^{32},
  401. 2^{40}, 2^{48}, 2^{56}$.  For all of these $N$, the mean of the cycle
  402. lengths computed across all experiments was close to an expected
  403. relative error of
  404. $(1/\sqrt{j}$ for $j$ experiments) of the expected cycle length.  
  405. We did not do this test with larger sets of keys because of the time
  406. constraints.
  407.  
  408. \begin{center}
  409. \begin{tabular}{lrrrrr}
  410. $N$ & \# of exps & Mean cycle len & Expec cycle len &
  411. Rel Err & Expec rel err \\
  412. \hline
  413. $2^{10}$ & 5000 & 20.4 & 20.1 & .019 & .014 \\
  414. $2^{16}$ & 3000 & 164.7 & 160.4 & .027 & .018 \\
  415. $2^{24}$ & 2000 & 2576.6 & 2566.8 & .004 & .022 \\
  416. $2^{32}$ & 2000 & 40343.2 & 41068.6 & .018 & .022 \\
  417. $2^{40}$ & 1000 & 646604.9 & 657097.6 & .016 & .032 \\
  418. $2^{48}$ & 10 & 8,980,043 & 10,513,561 & .145 & .316 \\
  419. $2^{56}$ & 1 & 28,767,197 & 168,216,976 & .829 & 1 \\
  420. \end{tabular}
  421. \end{center}
  422.  
  423. {\bf A.2 Statistical Randomness and Correlation Tests}
  424.  
  425. The second set of tests examined whether there were any correlations
  426. between the input and output of SKIPJACK, or between a key and the
  427. output.  We also looked for nonrandomness in functions of the form
  428. $SJ(k,m) \oplus SJ(k,m \oplus h)$ and functions of the form $SJ(k,m) \oplus
  429. SJ(k \oplus h , m)$ for all $h$ of Hamming weight 1 and 2 and for some
  430. randomly chosen $h$.  All results were consistent with these functions
  431. behaving like random functions.
  432.  
  433. Given a set of $N$ numbers of $k$-bits each, a chi-square test will
  434. test the hypothesis that this set of numbers was drawn (with
  435. replacement) from a uniform distribution on all of the $2^k$, $k$-bit
  436. numbers.  We ran the tests using a 99\% confidence level.  A truly
  437. random function would pass the test approximately 99\% of the time.
  438. The test is not appropriate when $N/2^k$ is too small, say $\leq 5$.
  439. Since it was infeasible to run the test for $k = 64$, we would pick 8
  440. bit positions, and generate a set of $N= 10,000$ numbers, and run the
  441. test on the $N$ numbers restricted to those 8 bit positions (thus
  442. $k=8$).  In some of the tests, we selected the 8 bits from the output
  443. of the function we were testing, and in others, we selected 4 bits
  444. from the input and 4 from the output.
  445.  
  446. Some of the tests were run on both the encryption and decryption
  447. functions of SKIPJACK.  The notation $SJ^{-1}(k,m)$ will be used to
  448. denote the decryption function of SKIPJACK with key $k$ on message
  449. $m$.
  450.  
  451. {\bf Test 1: Randomness test on output.  } In a single test: Fix $k$,
  452. fix mask of 8 output bits, select 10,000 random messages, run
  453. chi-square on the 10,000 outputs restricted to the mask of 8 output
  454. bits.  Repeat this single test for 200 different values of $k$ and 50
  455. different masks, for a total of 10,000 chi-square tests.  We found
  456. that .87\% of the tests failed the 99\% confidence level chi-square
  457. test.  This is within a reasonable experimental error of the expected
  458. value of 1\%.  On the decryption function, there were only .64\% of
  459. the tests that failed.  This was on a much smaller test set.
  460.  
  461. \begin{center}
  462. \begin{tabular}{|c|c|c|c|c|}
  463. \hline
  464. \# $k$  & \# masks &  function, $f(m)$ & mask & \% failed \\
  465. \hline
  466. 200 & 50 & $SJ(k,m)$ & 8 of $f(m)$ & .87 \\
  467. \hline
  468. 25 & 50 & $SJ^{-1}(k,m)$ & 8 of $f(m)$ & .64 \\
  469. \hline
  470. \end{tabular}
  471. \end{center}
  472.  
  473. {\bf Test 2: Correlation test between messages and output.}
  474. Single test:  Fix $k$, fix mask of 4 message bits and 4 output bits,
  475. select 10,000 random messages, run chi-square.
  476.  
  477. \begin{center}
  478. \begin{tabular}{|c|c|c|c|c|}
  479. \hline
  480. \# $k$  & \# masks &  function, $f(m)$ & mask & \% failed \\
  481. \hline
  482. 200 & 1000  & $SJ(k,m)$ & 4 of $m$, 4 of $f(m)$ & 1.06 \\
  483. \hline
  484. 25 & 1000 & $SJ^{-1}(k,m)$ & 4 of $m$, 4 of $f(m)$ & 1.01 \\
  485. \hline
  486. \end{tabular}
  487. \end{center}
  488.  
  489. {\bf Test 3: Randomness test on the xor of outputs, given a fixed xor of
  490. inputs.  }
  491. Single test: Fix $k$, fix mask of 8 output bits, select 10,000 random
  492. messages. 
  493. Let $\cal H$ be the union of all 64 bit words of Hamming
  494. weight 1 (64 of these), all 64 bit words of Hamming weight 2 (2016 of
  495. these), and some randomly chosen 64 bit words (920 of these).
  496. Repeat this single test for all $h \in \cal H$, 50 different masks,
  497. and  4 different values
  498. of $k$.
  499.  
  500. \begin{center}
  501. \begin{tabular}{|c|c|c|c|c|c|}
  502. \hline
  503. \# $k$  & \# masks  & \# $h$ &  function, $f(m)$ & mask & \% failed \\
  504. \hline
  505. 4 & 50 & 3000 & $SJ(k,m) \oplus SJ(k,m \oplus h)$ & 8 of $f(m)$ & .99 \\
  506. \hline
  507. \end{tabular}
  508. \end{center}
  509.  
  510.  
  511. {\bf Test 4: Correlation test between message xors and output xors.  }
  512. Single test: Fix $k$, fix mask of 4 bits of $h$ and 4 bits of output,
  513. select 10,000 random $(m,h)$ pairs.
  514.  
  515. \begin{center}
  516. \begin{tabular}{|c|c|c|c|c|}
  517. \hline
  518. \# $k$  & \# masks &  function, $f(m,h)$ & mask & \% failed \\
  519. \hline
  520. 200 & 1000 & $SJ(k,m) \oplus SJ(k,m \oplus h)$ & 4 of $h$, 4 of $f(m,h)$
  521. & .99 \\
  522. \hline
  523. 25 & 1000 & $SJ^{-1}(k,m)  \oplus SJ^{-1}(k,m \oplus h)$ & 4 of $h$, 4 of
  524. $f(m,h)$ & 1.02 \\
  525. \hline
  526. \end{tabular}
  527. \end{center}
  528.  
  529. {\bf Test 5: Correlation test between messages and output xors.}
  530. Single test: Fix $k$, fix mask of 4 bits of $m$ and 4 bits of output
  531. xor, select 10,000 random messages.  Let $\cal H$ be the union of all
  532. 64 bit words of Hamming weight 1 (64 of these), some of the 64 bit
  533. words of Hamming weight 2 (100 of these), and some randomly chosen 64
  534. bit words (100 of these).
  535.  
  536. \begin{center}
  537. \begin{tabular}{|c|c|c|c|c|c|}
  538. \hline
  539. \# $k$  & \# masks & \# $h$&  function, $f(m)$ & mask & \% failed \\
  540. \hline
  541. 2 & 1000 & 264 & $SJ(k,m) \oplus SJ(k,m \oplus h)$ & 4 of $m$, 4 of $f(m)$
  542. & .99 \\
  543. \hline
  544. \end{tabular}
  545. \end{center}
  546.  
  547. {\bf Test 6: Correlation test between keys and output.}
  548. Single test:  Fix $m$, fix mask of 4 key bits and 4 output bits,
  549. select 10,000 random keys.
  550.  
  551. \begin{center}
  552. \begin{tabular}{|c|c|c|c|c|}
  553. \hline
  554. \# $m$ & \# masks &  function, $f(k)$ & mask & \% failed \\
  555. \hline
  556. 200 & 1000  & $SJ(k,m)$ & 4 of $k$, 4 of $f(k)$ & 1.00 \\
  557. \hline
  558. 25 & 1000 & $SJ^{-1}(k,m)$ & 4 of $k$, 4 of $f(k)$ & 1.02 \\
  559. \hline
  560. \end{tabular}
  561. \end{center}
  562.  
  563. {\bf Test 7: Randomness test on the xor of outputs, given a fixed xor of
  564. keys.  }
  565. Single test: Fix $m$, fix mask of 8 output bits, select 10,000 random
  566. keys. 
  567. Let $\cal H$ be the union of all 80 bit words of Hamming
  568. weight 1 (80 of these), all 80 bit words of Hamming weight 2 (3160 of
  569. these), and some randomly chosen 80 bit words (760 of these).
  570. Repeat this single test for all $h \in \cal H$, 50 different masks,
  571. and  2 different values
  572. of $m$.
  573.  
  574. \begin{center}
  575. \begin{tabular}{|c|c|c|c|c|c|}
  576. \hline
  577. \# $m$ & \# masks  & \# $h$ &  function, $f(k)$ & mask & \% failed \\
  578. \hline
  579. 2 & 50 & 4000 & $SJ(k,m) \oplus SJ(k\oplus h,m )$ & 8 of $f(k)$ & .99 \\
  580. \hline
  581. \end{tabular}
  582. \end{center}
  583.  
  584.  
  585. {\bf Test 8: Correlation test between key xors and output xors.  }
  586. Single test: Fix $m$, fix mask of 4 bits of $h$ and 4 bits of output,
  587. select 10,000 random $(k,h)$ pairs.
  588.  
  589. \begin{center}
  590. \begin{tabular}{|c|c|c|c|c|}
  591. \hline
  592. \# $m$ & \# masks &  function, $f(k,h)$ & mask & \% failed \\
  593. \hline
  594. 200 & 1000 & $SJ(k,m) \oplus SJ(k\oplus h,m )$ & 4 of $h$, 4 of $f(k,h)$
  595. & 1.02 \\
  596. \hline
  597. 25 & 1000 & $SJ^{-1}(k,m) \oplus SJ^{-1}(k\oplus h,m )$ & 4 of $h$, 4
  598. of $f(k,h)$ & 1.1 \\
  599. \hline
  600. \end{tabular}
  601. \end{center}
  602. \end{document}
  603.